This invention relates to digital filters useful in environments where power consumption must be reduced such as in wireless telephone systems, and, more particularly, in code division multiple access (CDMA) wireless telephone terminals.
Finite impulse response (FIR) filters can be implemented in several forms, the most popular of which are the transversal and direct implementations. An FIR filter of order N performs the dot product of a received sample vector [y(n)] and a filter coefficient vector [X(n)], both of length N. The received filter vector, made up of values stored in registers (memory elements) of the filter, is updated each clock cycle by eliminating the oldest value in the vector, shifting the received filter vector values toward the position of the eliminated value, and appending the new filter value at the opposite end of the received filter vector. The successive dot products create an FIR convolution.
More specifically, when a transversal filter is implemented with filter coefficients (tap weight vectors) that are either xe2x88x921 or 1, the output function, Cn, of the filter may be mathematically described by the equation:                               C          n                =                              ∑                          k              =              0                                      N              -              1                                ⁢                                    y              ⁡                              (                                  n                  -                  k                                )                                      ·                          x              ⁡                              (                k                )                                                                        eq        .                  xe2x80x83                ⁢        1            
where, Cn is the filter output; y(nxe2x88x92k) is the filter input at time nxe2x88x92k; x(k) is the filter coefficient for the kth stage of the filter; and N is the number of stages in the filter; with each stage including at least one multiplier. At each clock cycle, for each stage of the filter, the incoming sample is multiplied by the filter coefficient for that stage. Each resulting product, which is the weighted sample input for a stage, is added to the value of its respective preceding stage of the filter, or zero if there is no preceding stage, and stored for use on the next clock cycle.
FIG. 1 shows an exemplary, prior art, N-stage transversal filter for performing such FIR filtering with coefficients that are either xe2x88x921 or 1. Each stage includes a two input multiplier (101i), a register (105i) and a two input port adder (103i). Each multiplier 101i multiplies an incoming sample y(n) with a respective one of filter coefficients X0 through XNxe2x88x921. The output of each multiplier 101i is supplied to an input port of a corresponding adder 103i, except for the output of multiplier 101-N receiving coefficient XNxe2x88x921, whose output is supplied directly to the input of register 105(Nxe2x88x921) furthest from output Cn. The output of multiplier 101-N, receiving coefficient XNxe2x88x921 is supplied directly to the input of register 105(Nxe2x88x921) because there is no prior stage of the filter to feed into this stage, and so, if this stage had an adder, its inputs would be the sample and 0, which renders its function unnecessary. One input port of each adder (103i) is supplied with the output of its corresponding multiplier (101i), and the other input port is supplied with the output that was stored during the immediately preceding clock cycle in its corresponding register 105i. 
The adder 103i of each stage sums the outputs of its multiplier 101i and the outputs of its associated register 105i. The output port of each adder is connected to the input port of the next register 105 along the filter chain towards the output Cn.
To implement the output function Cn of eq. 1, the input samples [y(n)] are multiplied by filter coefficients [X(n)] selected to be either 1 or xe2x88x921. To effectuate this computation using a two""s complement operation results in several problems associated with the circuit of FIG. 1, which may be explained by reference to FIGS. 1A, 1B, 1C and 1D and by noting that each input sample is comprised of a number of bits. For purpose of illustration, it is assumed that each input sample consists of 4 bits (e.g., A0, A1, A2, A3). Note also that in order to multiply the input samples by filter coefficients of 1 and xe2x88x921, each multiplier 101 must include, for each bit being multiplied, a summing circuit, 12, and a carry circuit, 13, as shown for blocks 11a, 11b, 11c, and 11d in FIG. 1A. The summing circuit 12, for each multiplier bit, may be implemented as shown in FIG. 1B and the carry circuit 13, for each multiplier bit, may be implemented as shown in FIG. 1C.
Furthermore, as shown in FIG. 1D, each multiplier 101i may be required to have five outputs; i.e., one output for each of the four bits and one output for the carry. This requires that even the left most register (105-Nxe2x88x921) in FIG. 1 may need five inputs. Consequently, even register 105-Nxe2x88x921 may need to have five (5) outputs coupled to the next adder down the line. The next adder down the line must be capable of adding the outputs of its associated register and the outputs of its associated multiplier resulting in an increasing number of outputs being supplied down the filter chain. Hence, as a result, the size of the adders and registers along the filter chain increase and, where a filter has a large number of stages, the size of the adders and registers may increase substantially.
Therefore it is evident from FIGS. 1A, 1B, 1C and 1D that the multiplier circuitry for enabling multiplication by coefficients which are 1 or xe2x88x921 is highly complex. It should also be noted that a significant amount of power is dissipated in the multiplier circuit due to the substantial amount of switching being performed by the highly complex circuitry. In addition, there is also a significant amount of switching and ensuing power dissipation in the adder circuits (103-i) along the filter chain.
By way of example, it may be desirable to form these filter circuits using complementary metal oxide semiconductor (CMOS) components because of their extremely low power consumption; i.e., they do not consume power when the bit values in the circuits are constant. However, when CMOS circuits are switched (toggled) in value, i.e., changed from 0 to 1 or from 1 to 0, power is consumed. Applicants recognized that when the filter coefficients call for multiplication by xe2x88x921, as is required by the prior art filter, many bits are caused to change in value. So does the rippling of changes in bit values while adders 103 perform their calculations. All of these bit changes cause a substantial amount of power consumption even when the circuits of FIG. 1 are implemented using CMOS components.
Moreover, in the case where noise is expected at the output of the filter, the values at the intermediate stages in the prior art filter will be in the neighborhood of zero, and so the values are often changing between small positive and negative values. These changes in value result in a large number of the bits which are used to represent the values toggling from 0 to 1 or from 1 to 0. This toggling causes power consumption even when the circuits of FIG. 1 are implemented using CMOS circuitry.
Applicants recognized that a high level of circuit complexity and a high degree of power dissipation exists in the filter circuit formed in accordance with the prior art because the filter coefficients (or tap weight vectors) were selected to be either 1 or xe2x88x921.
Applicants"" invention resides, in part, in the recognition that the multipliers (101) in the circuit of FIG. 1 may be greatly simplified with much power savings and that the power dissipated in the adders (103) may also be greatly reduced by having a first filter section whose filter coefficients are made either 1 or zero (rather than 1 and xe2x88x921) in order to produce a first output (i.e., C1) and by adding a compensation network for producing a second output (i.e., C2), which when combined (added to or subtracted from) with the first output produces the output function (i.e., Cn) of equation 1, above.
Applicants invention also resides, in part, in the recognition that equation 1 may be recast as a first summation to produce a first output (C1) and a second summation to produce a second output (C2), and that C1 and C2 may be combined (added or subtracted) to produce the desired filter output (Cn) specified in eq. 1, above.
Applicants recognized that eq. 1 which represents the dot product of the received sample vector and the filter coefficient (tap weight) vector may be rewritten as:                                           C            n                    =                      2            ⁡                          [                                                                    ∑                                          k                      =                      0                                                              N                      -                      1                                                        ⁢                                                            y                      ⁡                                              (                                                  n                          -                          k                                                )                                                              ·                                                                                            x                          ⁡                                                      (                            k                            )                                                                          +                        1                                            2                                                                      -                                                      1                    2                                    ⁢                                                            ∑                                              k                        =                        0                                                                    N                        -                        1                                                              ⁢                                          y                      ⁡                                              (                                                  n                          -                          k                                                )                                                                                                        ]                                      ;                            eq        .                  xe2x80x83                ⁢        A            
Which can alternatively be written as:                                           C            n                    =                      [                                          2                ⁢                                                      ∑                                          k                      =                      0                                                              N                      -                      1                                                        ⁢                                                            y                      ⁡                                              (                                                  n                          -                          k                                                )                                                              ·                                                                                            x                          ⁡                                                      (                            k                            )                                                                          +                        1                                            2                                                                                  -                                                ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                  y                  ⁡                                      (                                          n                      -                      k                                        )                                                                        ]                          ;                            eq        .                  xe2x80x83                ⁢        B            
where Cn is the filter output; y(nxe2x88x92k) is the filter input at time nxe2x88x92k; x(k) is the filter coefficient for the kth stage of the filter which may be xe2x88x921 or 1; and N is the number of stages in the filter. Thus, the effective new coefficients                     x        ⁡                  (          k          )                    +      1        2    ,
may be represented as {tilde over (x)}(k), where {tilde over (x)}(k) takes on values of 0 or 1. In other words, the dot product may be written as:                                                                         C                n                            =                              2                ⁡                                  [                                                                                    ∑                                                  k                          =                          0                                                                          N                          -                          1                                                                    ⁢                                                                        y                          ⁡                                                      (                                                          n                              -                              k                                                        )                                                                          ·                                                                              x                            ~                                                    ⁡                                                      (                            k                            )                                                                                                                -                                                                  1                        2                                            ⁢                                                                        ∑                                                      k                            =                            0                                                                                N                            -                            1                                                                          ⁢                                                  y                          ⁡                                                      (                                                          n                              -                              k                                                        )                                                                                                                                ]                                                                                                                        =                                  2                  ⁡                                      [                                          C1                      -                                                                        1                          /                          2                                                ⁢                                                  xe2x80x83                                                ⁢                        C2                                                              ]                                                              ,                                                          eq        .                  xe2x80x83                ⁢        2            
which can alternatively be written as:                               C          n                =                              [                                          2                ⁢                                                      ∑                                          k                      =                      0                                                              N                      -                      1                                                        ⁢                                                            y                      ⁡                                              (                                                  n                          -                          k                                                )                                                              ·                                                                  x                        ~                                            ⁡                                              (                        k                        )                                                                                                        -                                                ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                  y                  ⁡                                      (                                          n                      -                      k                                        )                                                                        ]                    =                                    [                                                2                  ⁢                  C1                                -                C2                            ]                        .                                              eq        .                  xe2x80x83                ⁢        3            
The output function Cn may thus be expressed as a function of two products C1 and C2; where             C1      =                        ∑                      k            =            0                                N            -            1                          ⁢                              y            ⁡                          (                              n                -                k                            )                                ·                                                    x                ⁡                                  (                  k                  )                                            +              1                        2                                ;    and        C2    =                  ∑                  k          =          0                          N          -          1                    ⁢                        y          ⁡                      (                          n              -              k                        )                          .            
Advantageously, a filter structure implementing the filtering according to either equations 2 or 3 consumes less power, and is simpler, than the filter structure of the prior art. In particular, in a filter formed according to equation 2 or 3, multiplication by xe2x88x921 is eliminated, thus reducing power consumption from the changes in bit values necessitated by such multiplication and simplifying the structure. Additionally, the values at the adders of the intermediate stages of the filter used to form the product C1 are in the neighborhood of some mid-range value, rather than zero. As a result, the number of bits that change state is reduced, which, advantageously, further reduces the power consumption of the FIR filter.
Applicants"" invention also resides in the recognition that the xe2x80x9cmultipliersxe2x80x9d in each stage of an N-stage FIR filter section, where the filter coefficients are either 1 or 0, may take the form of relatively simple logic elements to produce a first element (C1).
Applicants"" invention also resides in the recognition that, in an N-stage FIR filter, an adder for summing the outputs of a multiplier of a stage with the outputs of the register of that stage may be by-passed when the filter coefficient applied to the multiplier of that stage is 0. This feature enables a substantial reduction in the power dissipation of the adders needed to supply signals to the subsequent registers along the filter chain.
Thus, where the adder of a stage adds (sums) the outputs of its associated multiplier with the outputs of its associated (first) register and supplies a summed output to the inputs of a subsequent (second) register along the filter chain, the adder of the stage may be bypassed for certain operating conditions. Thus, when an adder is connected between the outputs of a first register and the inputs to a second register, the adder may be bypassed in several different ways. In one embodiment, a first selectively enabled gating circuit (e.g., T3 in FIG. 4) may be coupled between the outputs of the first register and the inputs of the second register for, when enabled, shunting the adder. In another embodiment of the invention, a second selectively enabled gating circuit (e.g., T2 in FIG. 4) may be coupled between the outputs of the adder and the inputs to the second register. In still a third embodiment, a third selectively enabled gating circuit (e.g., T1 in FIG. 4) may be coupled between the outputs of the first register and the inputs to the adder. When the filter coefficient applied to the multiplier of a stage is 1 (or 0), the first gating circuit is disabled and the second and third gating circuits, when present, are enabled. When the filter coefficient applied to the multiplier of a stage is 0 (or 1), the first gating circuit is enabled to directly couple the outputs of the first register to the inputs of the second register and the second and third gating circuits, when present, are disabled to decouple the adder from the filter circuit. The adder networks which are bypassed should not dissipate any power. Statistically, half of the filter coefficients will be 0, hence in comparison to the prior art there is a substantial savings in the power dissipated by the adder circuitry along the filter chain.